#!/usr/bin/env python
# coding=utf-8

from nlp.CoreNLPClient import Parse, Ssplit
from utils.sexp import loads
from itertools import takewhile
import re
from pprint import pprint
import networkx as nx
version_special_list = ['update', 'beta', 'patch', 'patches', 'versions', 'alpha', 'final', 'hotfix', 'lite', 'patchlevel', 'version', 'build', 'gold', 'earlier', 'older']
with open("input/replace_list.txt") as f:
    replace_list = f.read().split('\n')
    replace_map = {x.split('|')[0].lower():x.split('|')[1].strip() for x in replace_list if x.strip()}

replace_regex = r"\b({})\b".format('|'.join(x if "-" not in x else x.replace('-', '\\-') for x in replace_map.keys()))

def sexpr_flatten(sexpr):
    if type(sexpr) is not list:
        if sexpr=="-LRB-":
            return "("
        if sexpr=="-RRB-":
            return ")"
        if sexpr=="-LSB-":
            return "["
        if sexpr=="-RSB-":
            return "]"
        return sexpr
    return ' '.join(sexpr_flatten(x) for x in sexpr[1:])

class Word:
    def __init__(self, word, POStag=None, attrib={}):
        self.word = word
        self.POStag = POStag
        self.attrib = attrib
    
    def __str__(self):
        if not self.attrib:
            return self.word
        elif self.POStag == 'IN' and 'ADVP' in self.attrib:
            return ' '.join([self.attrib['ADVP'], self.word])
        return self.word
    
    def __repr__(self):
        return str(self)

class ConjWords:
    def __init__(self, conj, words):
        self.words = words
        self.conj = conj

    def __str__(self):
        return "(||)".join([str(x) for x in self.words])

    def __repr__(self):
        return str(self)

class WordWithVersion:
    def __init__(self, word, version):
        self.word = word
        self.version = version

    def __str__(self):
        return ' '.join([str(self.word), self.version])

    def __repr__(self):
        return "WordWithVersion[word={},version={}]".format(self.word, self.version)

class Version:
    def __init__(self, prep, versions):
        self.prep = prep
        self.versions = versions

    def __str__(self):
        if self.prep:
            if len(self.versions)>1:
                return " {} ".format(self.prep).join(str(x) for x in self.versions)
            else:
                return ' '.join([self.prep, str(self.versions[0])])
        else:
            return ' '.join(str(x) for x in self.versions)

    def __repr__(self):
        return str(self)

def preProcess(text):
    words = {}

    # 句尾的句号经常在双引号前面，给后面也加一个便于分句
    text = text.replace('."', '." .')

    # 对这种不太符合我们对"."的判断逻辑的词做特殊处理
    # if "e.g." in text:
    #     key = "wordforreplace%d" % len(words)
    #     words[key] = "e.g."
    #     text = text.replace("e.g.", key) 
    text = text.replace("e.g.", "like")

    # 切分以逗号和句号和冒号结尾的词
    for x in re.findall(r'([^|\s][^\s]+\.)(?:\s|$)',text):
        text = text.replace(x, x.strip(".") + " .")
    for x in re.findall(r'([^|\s][^\s]+,)(?:\s|$)',text):
        text = text.replace(x, x.strip(",") + " ,")
    for x in re.findall(r'([^|\s][^\s]+:)(?:\s|$)',text):
        text = text.replace(x, x.strip(":") + " :")

    # 将形如(1)(2)(3)的tag短句替换
    if re.findall(r"(\(\d\))", text):
        pieces = re.split(r"(\(\d\))", text)
        pieces = [x.strip() for x in pieces[1:]]
        for i in range(len(pieces)/2):
            tag = pieces[i*2]
            if i == len(pieces)/2-1:
                # 添加边界约束, 对最后一个分句限定范围
                t = re.split(r"\s[\.,;]|or|and|in|if\s", pieces[i*2+1])[0]
            else:
                t = pieces[i*2+1]

            t = t.strip()

            changed = True
            while changed:
                changed = False
                if t.endswith(","):
                    t = t[:-1].strip()
                    changed = True
                if t.endswith("the"):
                    t = t[:-3].strip()
                    changed = True
                if t.endswith(" a"):
                    t = t[:-1].strip()
                    changed = True
                if t.endswith("or"):
                    t = t[:-2].strip()
                    changed = True
                if t.endswith("and"):
                    t = t[:-3].strip()
                    changed = True


            key = "wordforreplace%d" % len(words)
            text = text.replace(t,'{}'.format(key))
            text = text.replace(tag, "")
            words[key] = "{}".format(t)

    # 对括号中的内容进行替换
    # 如果不加上括号进行替换，容易把括号外的一些相同词给换掉出车祸
    for x in re.findall(r"([\w\.]*\([^\)]*\))[\w\.]*", text):
        key = "wordforreplace%d" % len(words)
        if x.strip().startswith("(") and x.strip().endswith(")"):
            text = text.replace(x,'({})'.format(key))
            words[key] = x.strip("()")
        else:
            text = text.replace(x,key)
            words[key] = x

    # 对双引号中的内容进行替换
    for x in re.findall(r"(\"[^\)]*\")", text):
        key = "wordforreplace%d" % len(words)
        words[key] = x
        text = text.replace(x,key) 

    tokens = text.strip().split()

    # method、function之前的单词预先替换掉以保证其为名词
    result = []
    for i, x in enumerate(tokens):
        if i<len(tokens)-1 and tokens[i+1] in ['method', 'function', 'command']:
            key = "wordforreplace%d" % len(words)
            words[key] = x
            result.append(key)
        else:
            result.append(x)
    tokens = result 

    # 除去与括号相邻的单词旁边的括号
    result = []
    for x in tokens:
        if x.endswith("()"):
            result.append(x)
            continue
        if x.startswith("("):
            result.append("(")
        if x.startswith(")"):
            result.append(")")
        result.append(x.strip("()"))
        if x.endswith(")"):
            result.append(')')
        if x.endswith("("):
            result.append('(')
    tokens = result    

    # 替换特殊的代表版本号的单词
    # 当且仅当相邻位置存在版本号时才替换
    # 需要在下一步替换之前进行，否则很多版本号数字已经被替换掉了
    result = []
    for i, x in enumerate(tokens):
        if x.lower() not in version_special_list:
            result.append(x)
        elif i>0 and isVersionNumber(tokens[i-1]):
            key = "version%d" % len(words)
            words[key] = x
            result.append(key)
        elif i<len(tokens)-1 and isVersionNumber(tokens[i+1]):
            key = "version%d" % len(words)
            words[key] = x.lower()
            result.append(key)
        else:
            result.append(x)

    tokens = result

    text = ' '.join(tokens)
    # 针对性对一些容易出错的词做处理
    verb_list = []
    noun_list = []

    def replace(match_obj):
        # 考虑到匹配时是忽略大小写的，而replace_map中全部都是小写的，此处需要转换为小写才能正确处理
        x = match_obj.group(0).lower()
        if replace_map[x] == 'V':
            verb_list.append(x)
            return "embellish"
 
        elif replace_map[x] == 'N':
            noun_list.append(x)
            return "draculaura"

    # print replace_regex
    text = re.sub(replace_regex, replace, text, flags=re.I)

    tokens = text.strip().split()


    result = []
    for x in tokens:
        # 将所有的带"."的词预先替换，以避免被Stanford Parser的分词系统分成不同的词
        # 也将所有以括号结束的词替换
        # 但要注意剔除掉"."结尾的词，这时候点是句号
        if x != "." and x != '..' and "." in x and not x.endswith(".") or x.endswith("()"):
            key = "wordforreplace%d" % len(words)
            words[key] = x
            result.append(key)
            continue
        # 在这里添加需要被替换的特殊字符时，要注意在flatten函数的最后添加相应的ignore
        for c in ['#', '+', '-', ',', '"', "'", ":", '/', '%', '~', '@', '^', '\\', '&', "|", "!", '=']:
            if x != c and c in x:
                key = "wordforreplace%d" % len(words)
                words[key] = x
                result.append(key)
                break
        else:
            result.append(x)
    tokens = result 

    # 将所有大写字母开头的单词和纯大写的单词替换
    # 它们更有可能是专有名词
    result = [tokens[0]]
    for x in tokens[1:]:
        # 只对字母组成的单词进行此步判断
        if not x.isalpha():
            result.append(x)
            continue
        if x.isupper() or x == x.capitalize():
            key = "wordforreplace%d" % len(words)
            words[key] = x
            result.append(key)
            continue
        else:
            result.append(x)
    tokens = result 

     
    return ' '.join(tokens), words, verb_list, noun_list
        



def isVersionNumber(s):
    # 特判的词表
    if s in ['mp4']:
        return False
    # 以"-"分割的版本号
    if "-" in s:
        parts = [isVersionNumber(x) for x in s.split("-")]
        if all(parts):
            return True
        return False
    # 日期与时间
    if re.findall(r"^\d{4}\-\d{2}-\d{2}$", s):
        return True
    if re.findall(r"^\d{2}:\d{2}$", s):
        return True
    # 带括号的版本号
    # e.g. 5.2(2)
    # 括号中必须有内容
    if re.findall(r"([\w\.]*\([^\)]+\))[\w\.]*", s, re.I):
        return True
    # SP后面紧跟一个数字，这种格式通常是Service Pack的缩写，为版本号
    if re.findall(r'^SP\d+$', s, re.I):
        return True
    # 普通的数字字母型的版本号,以.分割
    # Stanford Parser只能识别纯数字以点分割
    # e.g. 2.0.0.11, 3.0b2, 8.0.x
    if re.findall(r'^v?(?:[\d]+\.)+[a-z\d]+$', s, re.I):
        return True
    # 前面点分割后面带-的版本号
    # e.g. 1.11r11-rh2
    if re.findall(r'^v?(?:[\d]+\.)+[a-z\d\-_]+$', s, re.I):
        return True
    # 纯数字
    # 或者以v开头的数字
    if re.findall(r'^v?\d+$', s, re.I):
        return True
    # 纯大写字母+数字并且长度较短
    # e.g. R2
    if re.findall(r'^[A-Z]+\d+$', s, re.I) and len(s)<5:
        return True
    return False

def postProcess(tree, replace_map):
    '''
    对Parse得到的Tree进行各种必要的后期处理

    将乱七八糟的无实际意义的tag整合
    PRP$ JJR JJS -> JJ
    PRP NNS NNP NNPS -> NN
    RBR RBS -> RB 
    MD VBD VBP VBZ  -> VB

    同时对POS tag进行一些启发式的替换，以更正常出现的一些错误
    '''
    if type(tree) is not list:
        return
    if tree[0] in ['PRP$', 'VBN', 'JJR', 'JJS']: 
        tree[0] = 'JJ'
    elif tree[0] in ['PRP', 'NNS', 'NNP', 'NNPS']:
        tree[0] = 'NN'
    elif tree[0] in ['RBR', 'RBS']:
        tree[0] = 'RB'
    elif tree[0] in ['MD', 'VBD','VBP','VBZ']:
        tree[0] = 'VB'

    if type(tree[1]) is not list:
        # 将前面替换掉的用于防止出现问题的字段替换回来
        if tree[1] in replace_map:
            if tree[1].startswith("version"):
                tree[0] = 'CD'
            tree[1] = replace_map[tree[1]]
            
        # 标定版本号
        if isVersionNumber(tree[1]):
            tree[0] = 'CD'
        # 处理一些被POS误判为CD的情况
        # 注意此处必须写NN而不能写NP，NP会被后续的flatten给忽视掉
        elif tree[1] not in version_special_list and tree[0] == 'CD':
            tree[0] = 'NN'
    for x in tree[1:]:
        postProcess(x, replace_map)


def flatten(tree):   
    if tree[0] in ['NP','ADJP']:
        result = []
        for x in tree[1:]:
            result.extend(flatten(x))
        return result
    if tree[0] in ['S','FRAG','QP']:
        result = []
        for x in tree[1:]:
            result.extend(flatten(x))
        return result
    if tree[0] == 'PP':
        # 对于副词开头的情况特殊处理
        # 将该副词添加到介词的属性中
        # e.g. mostly in Linux
        if tree[1][0] == 'ADVP':
            result = [(tree[2][0], Word(tree[2][1], POStag=tree[2][0]  ,attrib={'ADVP': sexpr_flatten(tree[1])}) )]
            for x in tree[3:]:
                result.extend(flatten(x))
        elif tree[1][0] in ['IN', 'VBG', 'TO']:
            result = [(tree[1][0], tree[1][1])]
            for x in tree[2:]:
                result.extend(flatten(x))
        else:
            result = []
            for x in tree[1:]:
                result.extend(flatten(x))
        return result
    if tree[0] == 'IN':
        # 忽略单独出现的if
        if tree[1] == 'if':
            return []
        return [('IN', tree[1])]
    if tree[0] in ['VP', 'ADVP', 'UCP']:
        result = []
        for x in tree[1:]:
            result.extend(flatten(x))
        return result 
    # 我也不知道为什么，但确实有一些PRN并非只包着括号的内容
    if tree[0] == 'PRN':
        if tree[1][0] == '-LRB-':
            return [(tree[0], sexpr_flatten(tree))]
        else:
            result = []
            for x in tree[1:]:
                result.extend(flatten(x))
            return result

    # 这些符号多为终结符，直接输出它们
    if tree[0] in ['CD', 'CC', 'NN', 'NNS', 'NNP', 'VB', 'VBZ', 'VBP', 'VBG', 'VBN', 'TO', 'JJ', 'MD', 'EX']:
        return [(tree[0], sexpr_flatten(tree))]
    # 最终还是决定让副词们去死吧
    if tree[0] in ['RB']:
        return []
    # if tree[0] == 'ADJP':
        # e.g.due to
        # e.g. prior to 
        # return [(tree[0], sexpr_flatten(tree))]

    if tree[0] == 'SBAR':                                       
        if tree[1][0] in ['WHADVP', 'WHNP', 'WHPP'] or tree[1][1] in ['while', 'if']:   
            return [(tree[0], sexpr_flatten(tree))]
        else:
            result = []
            for x in tree[1:]:
                result.extend(flatten(x))
            return result
    if tree[0] in ['-LRB-', '-RRB-', ',', ';']:
        return [(tree[0], sexpr_flatten(tree))]
    # 这些符号对我们的解析并没有什么实质性的帮助，直接去掉就可以了
    if tree[0] in ['.', 'FW', 'DT', "#", "+", "-", "'", '"', ":", "/", '%', '~', '@', '^', '\\', '&', "|", "!"]:
        return []
    result = []
    for x in tree[1:]:
        result.extend(flatten(x))
    return result 

def merge(vec):
    # 对没有被包裹在PRN内的括号内容进行合并
    changed = True
    while changed:
        changed = False
        
        l_index = r_index = -1
        for i, x in enumerate(vec):
            if x[0] == '-LRB-':
                l_index = i
            if x[0] == '-RRB-':
                r_index = i

        if l_index != -1 and r_index != -1:
            result = vec[:l_index] + [('PRN', ' '.join(x[1] for x in vec[l_index+1:r_index]))] +vec[r_index+1:]    
            vec = result
            changed = True

    # 暂时放在这里，对预处理出了岔子的词组进行处理
    result = []
    for x in vec:
        if not result:
            result.append(x)
        elif x[1] == 'to' and result[-1][1] == 'prior':
                result[-1] = ('IN', ' '.join([result[-1][1], x[1]]))
                changed= True
        else:
            result.append(x)
    vec = result

    # 把相邻的JJ进行合并
    changed = True
    while changed:
        changed = False
        result = []
        for x in vec:
            if not result:
                result.append(x)
            elif x[0] in ['JJ'] and result[-1][0] in ['JJ']:
                result[-1] = ('JJ', ' '.join([result[-1][1], x[1]]))
                changed= True
            else:
                result.append(x)
        vec = result
    

    # 将前置的形容词、副词、冠词也合并, 并且将相邻的名词合并
    # e.g. "X.509 certificates"
    # e.g. "Possibly other versions"
    
    changed = True
    while changed:
        changed = False
        result = []
        for x in vec:
            if not result:
                result.append(x)
            # 是否让NP与前置的VBG合并仍需观察
            elif x[0] in ['NP','NNP', 'NN', 'NNS'] and result[-1][0] in ['JJ', 'NP', 'NNP', 'NN', 'NNS', 'RB', 'DT', 'ADJP']:
                result[-1] = ('NP', ' '.join([str(result[-1][1]), x[1]]))
                changed= True
            else:
                result.append(x)
        vec = result

    # 对特殊的版本号进行预修改
    changed = True
    while changed:
        changed = False
        result = []

        for x in vec:
            if len(result)<2:
                result.append(x)
            # before、after后面一般是版本号，不太确定
            elif x[0] in ['NN', 'NP'] and result[-1][1] in ['before', 'after']:
                result[-1] = ('CD', Version(result[-1][1], [x[1]]))
                changed = True
            #  对version后面紧跟的长得特别奇怪的词做特判
            elif x[0] in ['NN', 'NP', 'CD'] and result[-1][1] in ['version'] and re.findall(r'[\d\.]*', x[1]):
                result[-1] = ('CD', Version(None, [result[-1][1], x[1]]))
                changed = True    
            elif x[0] in ['CD'] and result[-1][0] == 'CD':
                result[-1] = ('CD', Version(None, [result[-1][1], x[1]]))
            else:
                result.append(x) 
        vec = result

    # 对名词与后缀的版本号进行合并
    changed = True
    while changed:
        changed = False
        result = []
        for x in vec:
            if not result:
                result.append(x)
            elif x[0] == 'CD' and result[-1][0] in ['NN', 'NP']:
                result[-1] = ('NP', WordWithVersion(result[-1][1], x[1]))
            else:
                result.append(x)
        vec = result
    

    # 将介词与前置的形容词和介词进行合并
    changed = True
    while changed:
        changed = False
        result = []
        for x in vec:
            if not result:
                result.append(x)
            # 是否让NP与前置的IN合并仍需观察
            elif x[0] == 'IN' and result[-1][0] in ['JJ', 'VBG', 'IN']:
                result[-1] = ('IN', ' '.join([result[-1][1], x[1]]))
                changed= True
            # 将JJ与后置的to合并成为介词
            # e.g. passed to 
            elif x[0] == 'TO' and result[-1][0] in ['JJ']:
                result[-1] = ('IN', ' '.join([result[-1][1], x[1]]))
            else:
                result.append(x)
        vec = result

    # 如果进行完上述的合并，还有单独出现的JJ，那么把它变成NP
    # 其中earlier, prior等特殊时序词作为版本号处理
    result = []
    for x in vec:
        if x[1] in ['earlier', 'prior', 'older']:
            result.append(('CD', x[1]))
        elif x[0] == 'JJ':
            result.append(('NP', x[1]))
        else:
            result.append(x)
    vec = result

    # 对特殊的版本号词进行合并
    changed = True
    while changed:
        changed = False
        result = []
        for x in vec:
            if len(result) < 1:
                result.append(x)
            elif x[1] in version_special_list and result[-1][0] == 'CD' or result[-1][1] in version_special_list and x[0] == 'CD':
                result[-1] = ('CD', ' '.join([result[-1][1], x[1]]))
                changed = True
            elif x[1] in ['version', 'versions'] and result[-1][1] in ['prior', 'other']:
                result[-1] = ('CD', ' '.join([result[-1][1], x[1]]))
                changed = True
            elif x[0] == 'CD' and result[-1][0] == 'RB':
                result[-1] = ('CD', ' '.join([result[-1][1], x[1]]))
                changed = True
            else:
                result.append(x)
        vec = result

    # 将相邻的动词词组也进行合并
    # 将动词词组与前导副词和后置的介词进行合并
    # 将动词与前置的TO也合并
    # e.g. rely on
    # e.g. does not mention
    # RB - Adverb
    # VB - Verb, base form
    # VBD - Verb, past tense
    # VBN - Verb, past participle
    # VBP - Verb, non-3rd person singular present
    # VBZ - Verb, 3rd person singular present
    # e.g. "does not verify"
    
    changed = True
    while changed:
        changed = False
        result = []
        for x in vec:
            if not result:
                result.append(x)
            elif x[0] in ['TO','RB','VB', 'VBZ', 'VBP', 'VBN', 'IN'] and result[-1][0] in ['RB', 'VB', 'VBZ', 'VBP', 'VBN']:
                # 仅对in结尾的词组和based on做这样的处理
                if x[0] == 'IN' and (x[1] == 'in' or x[1] == 'on' and result[-1][1]=="based"):
                    result[-1] = ('IN', ' '.join([result[-1][1], x[1]]))
                # 对 is vuln to 之类的词组也做介词化处理
                elif x[0] == 'IN' and result[-1][1] in ['is', 'was']:
                    result[-1] = ('IN', ' '.join([result[-1][1], x[1]]))
                else:
                    result[-1] = ('VB', ' '.join([result[-1][1], x[1]]))
                changed =True
            # 对there be句型的处理：直接忽略丢弃
            elif x[0] in ['VB', 'VBZ', 'VBP', 'VBN'] and result[-1][0] in ['EX']:
                result.pop(-1)
                changed = True
            else:
                result.append(x)
        vec = result

    
    # 将which开头的SBAR后面的内容都合并进从句
    index = -1
    for i, x in enumerate(result):
        if x[0] == 'SBAR' and x[1].startswith("which"):
            index = i
            break
    if index>-1:
        remains = [sexpr_flatten(t)[1] for t in result[index+1:]]
        # print remains
        result[index] = (x[0], x[1]+ ' '.join(remains))
        result = result[:index+1]

    # 特殊的从句合并逻辑
    # e.g. with shadowing enabled
    result = []
    for x in vec:
        if len(result)<2:
            result.append(x)
        elif x[1] == 'enabled' and result[-2][1] == 'with':
            result[-2] = ('SBAR', ' '.join([result[-2][1], result[-1][1], x[1]]))
            result.pop(-1)
        else:
            result.append(x)

    vec = result
    
    # 针对特定的介词进行合并
    # e.g. SP1 through SP6, SP7 through SP8
    # e.g. before 8.5.0.1
    # e.g. after 8.5.0.1
    changed = True
    while changed:
        changed = False
        result = []

        for x in vec:
            if len(result)<2:
                result.append(x)
            elif x[0] == 'CD' and result[-1][1] in ['through','before','after'] and result[-2][0] == 'CD':
                # result[-2] = ('CD', ('through', [result[-2][1], x[1]]))
                result[-2] = ('CD', Version(result[-1][1], [result[-2][1], x[1]]))
                result.pop(-1)
                changed = True
            elif x[0] == 'CD' and result[-1][1] in ['before', 'after', 'through', 'prior to']:
                # result[-1] = ('CD', '{} {}'.format(result[-1][1], x[1]))
                result[-1] = ('CD', Version(result[-1][1], [x[1]]))
                changed = True      
            else:
                result.append(x) 
        vec = result

    # 对连词进行合并
    # stat 1 相邻的动词
    # stat 2 相邻的版本号
    # stat 3 相邻的名词
    # (depracated)对to连接的名词进行合并
    changed = True
    while changed:
        changed = False
        result = []
        for x in vec:
            if len(result)<2:
                result.append(x)
            elif x[0] == 'VB' and result[-1][0] == 'CC' and result[-2][0] == 'VB':
                result[-2] = ('VB', ConjWords(result[-1][1], [x[1], result[-2][1]]))
                result.pop(-1)
                changed =True
            elif x[0] == 'CD' and result[-1][0] == 'CC' and result[-2][0] == 'CD':
                result[-2] = ('CD', ConjWords(result[-1][1], [x[1], result[-2][1]]))
                result.pop(-1)
                changed =True
            elif x[0] == 'CD' and result[-1][0] == 'CC' and isinstance(result[-2][1], WordWithVersion):
                wd = WordWithVersion(result[-2][1].word, Version(result[-1][1], [result[-2][1].version, x[1]]))
                result[-2] = ('NP', wd)
                result.pop(-1)
                changed = True
            elif x[0] in ['NN', 'NP'] and result[-1][0] == 'CC' and result[-2][0] in ['NN', 'NP']:
                result[-2] = ('NN', ConjWords(result[-1][1], [x[1], result[-2][1]]))
                result.pop(-1)
            # elif x[0] in ['NN', 'NP'] and result[-1][0] == 'TO' and result[-2][0] in ['NN', 'NP']:
            #     result[-2] = ('NN', ' to '.join([result[-2][1], x[1]]))
            #     result.pop(-1)
            else:
                result.append(x)
        vec = result


    return result


def buildGraph(vec):
    G = nx.DiGraph()

    node = None         # 上一个处理的待挂靠结点
    parent = None       # 上上个结点
    prep = None         # 即将使用的介词
    prep_used = None    # 使用过一次的介词
    cc_used = False     # 指示连词的当前使用状态
    vb = None           # 即将使用的动词
    vb_used = None      # 使用过一次的动词
    status = "Start"    # 当前状态
                        # Start 表示某个成分（subject或者object）的解析刚开始
                        # Node 表示刚解析完一个名词结点
                        # IN 表示正在解析一个介词短语
                        # VB 表示正在解析一个动词短语
    is_dummmy = False   # 表示现在的主语是否空缺
    previous_status = None  # 表示上一个状态
    last_vp_subj = None # 上一个动词短语的主语
    last_pp_subj = None # 上一个介词短语的主语
    processed_words = []    # 已经处理的词列表，最后一个为当前正在处理的词
    SUBJECT = "SUUUBBBJECT" # 特殊化的主语字符串，防止文本中出现相同的词
    OBJECT = "OOOBJEEECT"   # 特殊化的宾语字符串，防止文本中出现相同的词
    G.add_edge('ROOOOOOOT', SUBJECT, PREP="")
    root = SUBJECT
    node_chain = []
    

    for x in vec:
        processed_words.append(x)
        # print "word = {}, status = {}, node={}, previous_status={}, prep = {}, prep_used={}, is_dummy={}".format(x, status, node,previous_status,  prep, prep_used, is_dummmy)

        if x[0] in ['VBZ', 'VB', 'VBP', 'VBN']:
            if root == SUBJECT:
                last_vp_subj = root
                root = OBJECT
                # 对全句的谓词做一个专门的特殊标记
                G.add_edge(SUBJECT,root, PRED=x[1])
                previous_status = status
                status = "Start"

                # 如果出现了In Libtiff这种形式的定语前置句首，则特殊处理将其缀在最后
                if is_dummmy:
                    G.add_edge(node, dummy_node, PREP=dummy_prep)
                    prep_used = prep = None
                    is_dummmy = False
            else:
                if status != 'CC':
                    last_vp_subj = node
                else:
                    last_vp_subj = parent
                previous_status = status
                status = 'VB'
                vb = x[1]
            last_pp_subj = None
        elif x[0] in ['TO']:
            status = "IN"
            prep = "to"
            continue
        elif x[0] in ['NP', 'NNP', 'NN', 'NNS']:
            if status in ['Start']:
                G.add_edge(root, x[1], PREP="SUBJECT")
                node = x[1]
                previous_status = status
                status = "Node"
            elif status in ['Node']:
                if 'NMOD' not in G.node[node]:
                    G.node[node]['NMOD'] = [x[1]]
                else:
                    G.node[node]['NMOD'].append(x[1])
            elif status in ['IN', 'TO']:
                # 某些句子中last_vp_subj是不存在的，因为并没有VP
                # e.g. Information from SSL-encrypted sessions via PKCS #1.
                if prep in ['via', 'by']:
                    target = last_vp_subj if last_vp_subj else SUBJECT
                    G.add_edge(target, x[1], PREP=prep)
                    parent = target
                    node = x[1]
                    prep_used = prep
                    prep = None
                    last_pp_subj = target
                elif prep in ['of']:
                    if not last_pp_subj:
                        last_pp_subj = node
                    if 'of' not in G.node[node]:
                        G.node[node]['of'] = [x[1]]
                    else:
                        G.node[node]['of'].append(x[1])
                elif prep:
                    # 某些情况下，介词短语会在中心语之前出现，这种时候需要先用Dummy占位。 目前只考虑这种情况在句首出现
                    # e.g. In libavformat/mvdec.c in FFmpeg 3.3.3, a DoS in mv_read_header() 
                    # 否则直接将介词短语挂靠在最近的结点上即可
                    if node:
                        # if not ·last_pp_subj:
                        last_pp_subj = node
                        G.add_edge(node, x[1], PREP=prep)
                        parent = node
                        node = x[1]
                        prep_used = prep
                        prep = None
                    else:
                        # 将前置定语暂存，处理完这个NP链之后再将其挂在最后
                        is_dummmy = True
                        G.add_node(x[1])
                        dummy_prep = prep
                        dummy_node = node = x[1]
                        prep = None
                        status = "Start"
                else:
                    if 'NMOD' not in G.node[node]:
                        G.node[node]['NMOD'] = [x[1]]
                    else:
                        G.node[node]['NMOD'].append(x[1])
            elif status in ['VB']:
                G.add_edge(node, x[1], VB=vb)
                # 此处不更改node的值，因为紧接着的介词短语更可能是描述前面的VB的，因此要挂靠在前一个node上
                # 我也不知道这个逻辑是不是真的靠谱
                parent = node
                node = x[1]
                vb_used = vb
                vb = None
            elif status in ['CC']:
                # 如果前一个连词已经有名词挂载，那直接把现在的名词连接上去
                # 否则表明是一个新出现的名词
                if not cc_used:
                    if previous_status == 'Node':
                        G.add_edge(root, x[1], PREP="SUBJECT")
                        node = x[1]
                        cc_used = True
                    # 如果前面是一个IN NP CC NP的结构, 此时正在处理第二个NP
                    elif previous_status=='IN' and prep_used:
                        G.add_edge(parent, x[1], PREP=prep_used)
                        node = x[1]
                        cc_used = True
                    elif previous_status == 'VB' and vb_used:
                        G.add_edge(parent, x[1], VB=vb_used)
                        node = x[1]
                        cc_used = True
                else:
                    if 'NMOD' not in G.node[node]:
                        G.node[node]['NMOD'] = [x[1]]
                    else:
                        G.node[node]['NMOD'].append(x[1])
            else:
                raise RuntimeError("Unconsiderred status node={}, current={}, status={}, prep={}".format(node,x,status,prep))
        # 形容词短语分两种情况处理
        # 前面是个动词短语，类似make sth easier，则生成一个 sth----be----> easier的结构，make sth do 类比
        # 前面是个名词短语，则直接将其作为一个修饰词挂靠在那个结点上。注意如果前面是个PP，那应该挂载在整个PP的根部上
        elif x[0] == 'ADJP':
            if status in ['VB']:
                G.add_edge(node, x[1], VB="be")
            elif status:
                if last_pp_subj:
                    target = last_pp_subj
                else:
                    target = node
                if not target:
                    raise RuntimeError("Unconsiderred status node={}, current={}, status={}, prep={}".format(node,x,status,prep))

                if 'attrib' not in G.node[target]:
                    G.node[target]['attrib'] = [x[1]]
                else:
                    G.node[target]['attrib'].append(x[1])

        elif x[0] == 'SBAR':
            if x[1].startswith("that") or x[1].startswith("where") or x[1].startswith("with"):
                if 'condition' not in G.node[node]:
                    G.node[node]['condition'] = [x[1]]
                else:
                    G.node[node]['condition'].append(x[1])
            elif x[1].startswith("when"):
                if 'condition' not in G.node['ROOOOOOOT']:
                    G.node['ROOOOOOOT']['condition'] = [x[1]]
                else:
                    G.node['ROOOOOOOT']['condition'].append(x[1])
            elif x[1].startswith("which"):
                if 'result' not in G.node['ROOOOOOOT']:
                    G.node['ROOOOOOOT']['result'] = [x[1]]
                else:
                    G.node['ROOOOOOOT']['result'].append(x[1])
        elif x[0] == 'PRN':
            if 'MoreInfo' not in G.node[node]:
                G.node[node]['MoreInfo'] = [x[1]]
            else:
                G.node[node]['MoreInfo'].append(x[1])
        elif x[0] == 'CD': 
            # TODO: 权宜之计，见tag001
            if node:
                if 'version' not in G.node[node]:
                    G.node[node]['version'] = [x[1]]
                else:
                    G.node[node]['version'].append(x[1])
        # 当出现一个介词时
        # e.g. in, on, of
        elif x[0] in ['IN']:
            # TODO tag001
            if x[1] == 'of' and not node:
                continue
            previous_status = status
            status = 'IN'
            prep = x[1]
        elif x[0] in ['VBG']:
            if len(processed_words)>2 and processed_words[-2][0]=='IN':
                previous_status = status
                status = 'IN'
                prep = prep + ' ' +x[1]
            elif status in ['Node', 'CC', 'IN', 'VB']:
                previous_status = status
                status = 'IN'
                prep = x[1]
            
        elif x[0] in ['CC', ',', ';']:
            # 对In SunOS or Solaris, a remote user coul....这种主语后置的情况做特殊的处理
            if x[0] in [',', ';'] and is_dummmy:
                status = "Start"
            else:
                if status!='CC':
                    previous_status = status
                    status = 'CC'
                cc_used = False
        else:
            raise RuntimeError("Unconsiderred status node={}, current={}, status={}, prep={}".format(node,x,status,prep))

    # 如果完成处理后还有剩余的前置定语没有处理
    if is_dummmy:
        G.add_edge(node, dummy_node, PREP=dummy_prep)
        prep_used = prep = None
        is_dummmy = False

    # 对所有结点的内容做normlize
    for x in G.nodes():
        if isinstance(x, WordWithVersion):
            if 'version' in G.node[x]:
                p_version = G.node[x]['version']
            else:
                p_version = []
            G = nx.relabel_nodes(G, {x: x.word})
            G.node[x.word]['version'] = [x.version]
            G.node[x.word]['version'].extend(p_version)
    
    return G
            

def printGraph(G, root='ROOOOOOOT', depth=0):
    # 防止出现Error 202
    if depth>20:
        return ""
    result = ""
    result += "{}: {}\n".format(root, G.node[root])
    for x in G.adj[root]:
        if 'PREP' in G.edges[root, x]:
            result += "\t{}-----{}---->{}\n".format(root, G.edges[root, x]['PREP'], x)
        elif 'VB' in G.edges[root, x]:
            result += "\t{}-----{}---->{}\n".format(root, G.edges[root, x]['VB'], x)
        elif 'PRED' in G.edges[root, x]:
            result += "\t{}-----{}---->{}\n".format(root, G.edges[root, x]['PRED'], x) 
        else:
            result += "\t{}----------->{}\n".format(root, x)
    for x in G.adj[root]:
        result += printGraph(G, x, depth+1)
    return result

def getNodes(G, root='ROOOOOOOT', depth=0):
    # 防止出现Error 202
    if depth>20:
        return None
    result = []
    
    if root == "ROOOOOOOT":
        result.append(root)


    attribs = []
    
    for x in G.adj[root]:
        if 'PRED' in G.edges[root, x]:
            continue 

        if 'PREP' in G.edges[root, x] and G.edges[root, x]['PREP'] in ['via', 'by']:
            continue

        if 'PREP' in G.edges[root, x]:
            attribs.append(G.edges[root, x]['PREP'].lower())
    
    attribs = list(set(attribs))
    for attr in attribs:
        children = []

        for x in G.adj[root]:
            if 'PRED' in G.edges[root, x] or 'PREP' not in G.edges[root, x]:
                continue 

            if G.edges[root, x]['PREP'].lower() != attr:
                continue

            node_value = x

            # 部分仍含有NMOD遗留的结点，需要以特判的方式将NMOD的内容添加到输出当中
            if 'NMOD' in G.node[x]:
                node_value = ' '.join([node_value, ' '.join(G.node[x]['NMOD'])])
            if 'of' in G.node[x]:
                # 除类似Denial of Service以外的情况，of都是作为两个从属的词作为连接
                node_value = '|||'.join([node_value, '(||)'.join(G.node[x]['of'])])

            children.append(str(node_value))
        children = '(||)'.join(children)
        if not children:
            return result

        result.append(children)

    for x in G.adj[root]:
        if 'PRED' in G.edges[root, x]:
            continue 
        if 'PREP' in G.edges[root, x] and G.edges[root, x]['PREP'] in ['via' ,'by']:
            continue
        subnodes = getNodes(G, x, depth+1)
        if subnodes:
            result += subnodes
    return result

def pattern1(tree):
    """
    ROOT(S(NP))
    """
    assert tree[0] == 'ROOT'
    tree = tree[1]
    # pprint(tree)
    flattened = flatten(tree)
    # pprint(flattened)
    result = merge(flattened)
    #pprint(result)
    g = buildGraph(result)
    return g

                
def postProcess2(tree, verb_list, noun_list):
    '''
    与postProcess对应的还原函数
    '''
    if type(tree) is not list:
        return

    if type(tree[1]) is not list:
        # 将前面替换掉的用于防止出现问题的字段替换回来
        if 'embellish' in tree[1]:
            tree[1] = tree[1].replace('embellish', verb_list.pop(0))

        if 'draculaura' in tree[1] :
            tree[1] = tree[1].replace('draculaura', noun_list.pop(0))
            if tree[1] in ['version', 'versions', 'earlier', 'older']:
                tree[0] = 'CD'
    for x in tree[1:]:
        postProcess2(x, verb_list, noun_list)

def Pattern1Apply(text):
    # 暂时只对第一句话做处理
    origin_text = text
    text, replace_map, verb_list, noun_list = preProcess(text)
    
    result = Parse(text.encode("utf-8"))['sentences'][0]
    # print result['tokens'][6:9]
    tree = result['parse']
    # print tree
    basicdp = loads(tree)
    postProcess(basicdp, replace_map)
    postProcess2(basicdp, verb_list, noun_list)
    g = pattern1(basicdp)
    r = printGraph(g)
    # print 
#    print r
#    print origin_text
    return r, origin_text

def Pattern1Apply2(text):
    """
    同Pattern1Apply但return一个node list
    """
    origin_text = text
    text, replace_map, verb_list, noun_list = preProcess(text)

    result = Parse(text.encode("utf-8"))['sentences'][0]
    tree = result['parse']
    basicdp = loads(tree)
    postProcess(basicdp, replace_map)
    postProcess2(basicdp, verb_list, noun_list)

    g = pattern1(basicdp)
    # return nx.node_link_data(g)
    return getNodes(g)
    


def main():
    text = "Stack-based buffer overflow in the split_redraw function in split.c in mtr before 0.73, when invoked with the -p (aka --split) option, allows remote attackers to execute arbitrary code via a crafted DNS PTR record. NOTE: it could be argued that this is a vulnerability in the ns_name_ntop function in resolv/ns_name.c in glibc and the proper fix should be in glibc; if so, then this should not be treated as a vulnerability in mtr."
    tree = Parse(text)['sentences'][0]['parse']
    basicdp = loads(tree)

    print pattern1(basicdp)

    

if __name__=="__main__":
    main()

